LeetCode 120. Triangle

120.Triangle (三角形最小路径和)

链接

https://leetcode-cn.com/problems/triangle/

题目

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

思路

简单题，自顶向下或者自底向上方法都行，以第三行的5作为例子，自顶向下值有3,4能移动到它，之后也只能移动到1,8.只需要将能到达该点的两个数取最小的，加入这个数。

自顶向下：

第二行：3->3+2=5, 4->4+2=6

第三行：6->6+5->11, 5->5+min(5,6)=10, 7->7+6=13

第四行：4->4+11=15, 1->1+min(11,10)=11, 8->8+min(10,13)=18, 3->3+13=16.

最小和为11.

自底向上：

这样可以减少一些需要特殊考虑的地方，思路相同，只不过上下顺序变化，比如第三行的5，可以增加min（1,8），一直到最上层。

（这题思路简单，但是我敲的时候忘了List<List>要怎么用，贼尴尬）

代码

public int minimumTotal(List<List<Integer>> triangle) {
  for (int i = triangle.size() - 2; i >= 0; i--) {
    for (int j = 0; j < triangle.get(i).size(); j++) {
      int min = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));
      triangle.get(i).set(j, triangle.get(i).get(j) + min);
    }
  }

  return triangle.get(0).get(0);
}